# -*-coding = utf-8 -*-

# @Time: 2021/4/8 13:32
# @Author: bistro
# @File: p153.py
# @Software: PyCharm
# 153. 寻找旋转排序数组中的最小值
from typing import List


class Solution:
    """
    直接遍历O(n)
    二分查找
    """

    def findMin(self, nums: List[int]) -> int:
        length = len(nums)
        for i in range(length - 1):
            if nums[i] > nums[i + 1]:
                return nums[i + 1]
        return nums[0]

    def findMin(self, nums: List[int]) -> int:
        # 递归出口
        if len(nums) == 1:
            return nums[0]
        right = len(nums) - 1
        mid = right // 2
        if nums[mid] < nums[right]:
            return self.findMin(nums[0:mid+1])
        else:
            return self.findMin(nums[mid + 1:])

    def findMin(self, nums: List[int]) -> int:
        low, high = 0, len(nums) - 1
        while low < high:
            mid = low + (high - low) // 2
            if nums[mid] < nums[high]:
                high = mid
            else:
                low = mid + 1
        return nums[low]


